A digital image is basically a two-dimensional array of digital data with each entry representing a pixel of the digitized image. Pixel data contain intensity components like red, green, and blue (RGB). Display systems electronically assign intensity values to these different components based on input digital data. The displayed images, however, may have various optical and geometric distortions, such as lens distortions such as pincushion and barrel distortions, projection keystone distortions, and so on. One way to compensate for these distortions is digital image warping, or “non-uniform scaling”. Image warping may be defined as a process of dynamically resampling a regularly spaced input image to produce an output image with different spacing than the input image. Image warping is widely used in linear scaling operations like zoom and shrink, which are particular and simpler cases.
There are two basic stages in an image warping system: spatial transformation, and resampling.
A spatial transformation is defined as a mapping function between pixel coordinates in the input and output images. Inverse mapping, which specifies coordinates in the input image as a function of the coordinates in the output image, is usually used to cover the entire output image coordinate space and to avoid leaving “holes”.
Resampling, on the other hand, is the process of using several input pixels surrounding an input pixel to interpolate the output image pixels. The neighborhood containing these input pixels, which participate in the interpolation, is called filter footprint. It is well known in the art that the larger the filter footprint, the better the output image quality. In addition, anisotropic footprints are known to yield better output image quality. There is a trade off between the size and anisotropy of the footprint and the efficiency of the hardware implementation. Resampling is accomplished by dynamically band limiting the spatial frequency of the warped image to the Nyquist limit in all directions around the processed output pixel.
In order to reduce hardware resources required for filtering, image warping can be conducted in two separate horizontal and vertical passes. In this case the transformation must be separable (i.e., capable of being decomposed), into a sequence of two orthogonal, one-dimensional transformations. Examples of two-pass warping are used in U.S. Pat. Nos. 5,175,808, 5,594,676, and 6,061,477. The two-pass approach has many drawbacks however. Firstly, not all geometrical transformations are separable (bottleneck and fold over problems). Secondly, the separation itself may introduce geometrical distortions. Thirdly, two-pass filtering is prone to producing jagging artifacts, especially when the geometrical transformation has rotational component. Therefore, it is desirable to design a single-pass method for 2D image transformation (warping) that is free from disadvantages of the two-pass algorithm.
In multi-rate signal processing, in order to avoid unwanted artifacts, the resampling process of a digital image includes the following steps: reconstructing the continuous signal from its discrete samples, warping the continuous signal, low pass filtering the continuous signal to eliminate aliased frequencies above the normalized Nyquist frequency in the target image, and sampling the continuous warped signal at the output pixel grid sampling locations.
It is known in the art that these steps of the ideal resampling procedure may be concatenated into a single unified elliptical Gaussian filter called Elliptical Weighted Averaging [Paul S. Heckbert, “Fundamentals of Texture Mapping and Image Warping”, master Thesis, UCB, 1989]. Since then many efforts have been made to reduce needed hardware in terms of memory and clocks by using approximations of the ellipse radii.
U.S. Pat. No. 6,016,152, to Dickie, discloses apparatus and method for non-uniform image scaling approximated by corresponding affine transformation, which is used to define an ellipse in the source image. A linear transformation from a unit circle in the source image to the ellipse in the source image is calculated. A pixel value in the destination image is determined by identifying pixels included in the source image in order to reduce artifacts in non-uniform scaling applications.
U.S. Pat. No. 6,005,582, to Gabriel et. al., discloses method and system for texture mapping images with anisotropic filtering that includes passing an interpolating filter along a line of anisotropy in a texture map and computing a weighted sum of the outputs of the interpolating filter to compute pixel intensity values. The weighting of these output values can be computed using a one-dimensional digital filter. The line of anisotropy is derived from the inverse transform, which describes the mapping of a point on the surface of a geometric primitive to a point in the texture map.
U.S. Pat. No. 6,292,193, to Perry et. al., discloses techniques for anisotropic texture mapping using multiple space-invariant filtering operations per pixel. A circular pixel filter is projected onto a texture map to define an elliptical footprint in that texture map. Sample points are determined on a line in the footprint that closely approximates the major axis of the ellipse. These sample points are mapped to levels of detail and locations within mip-map. Using a space invariant filter, a texture value is computed for each sample point using data from one or more texture maps within mi-map. These texture values for the sample points are post-filtered using a Gaussian filter function and summed to produce a final texture value.
European Patent No. EP0920671B1, to Lohmeyer et. al., discloses method for computationally efficient single pass digital image warping that consists of the following stages: increasing the sampling rate of an input image above Nyquist rate, warping the upsampled image using a low quality interpolator such as a bilinear interpolator, and downsampling the warped image to the same resolution as the input image. Downsampling and warping stages can be combined into one step by modifying the geometric transformation function when warping the upsampled image.
However, these and other prior art systems provide a modest trade-off between aliasing and sharpness because their impulse responses produce pure frequency responses. Therefore, there is a need for an improved interpolation method and apparatus to support more flexible filtering in digital image warping system.